Shortest path algorithms.html (3615B)
1 <?xml version="1.0" encoding="UTF-8"?> 2 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> 3 <html><head><link rel="stylesheet" type="text/css" href="sitewide.css"><meta http-equiv="Content-Type" content="text/html; charset=UTF-8"/><meta name="exporter-version" content="Evernote Mac 7.1.1 (456663)"/><meta name="keywords" content="ng"/><meta name="altitude" content="-1.118819952011108"/><meta name="author" content="Alex Balgavy"/><meta name="created" content="2018-05-25 22:58:35 +0000"/><meta name="latitude" content="52.37361942175082"/><meta name="longitude" content="4.836354558355512"/><meta name="source" content="desktop.mac"/><meta name="updated" content="2018-05-26 16:06:59 +0000"/><title>Shortest path algorithms</title></head><body><div>Arcs in digraphs may carry negative weights. if there’s a cycle of negative weight, there are no shortest paths. Otherwise, there might be.</div><div><br/></div><div>Dijkstra’s (non-negative weights)</div><ul><li><div>used for link-state routing</div></li><li><div>fails if there are negative weights</div></li><li><div>to implement efficiently, you need Fibonacci heap data structure</div></li><li><div>the goal is shortest path to a node from every other node</div></li><li><div>algorithm (given that c is goal):</div></li><ol><li><div>S<span style="vertical-align: sub;">visited</span> = {}, H<span style="vertical-align: sub;">unvisited</span> = {a,b,…}, C<span style="vertical-align: sub;">goal</span>(0, F)</div></li><ul><li><div>add goal to visited, remove from unvisited</div></li><li><div>S = {c}</div></li><li><div>H = {a,b,d,e,f,g,h}</div></li><li><div>find neighbours of added node that have edges pointing to it — b(1,c), e(2,c)</div></li><li><div>choose lowest weight edge, add that node into visited set — b(1,c)</div></li><li><div>current distances:</div></li><ul><li><div>b(1,c)</div></li></ul></ul><li><div>S = {b,c}, H = {a,d,e,f,g,h}</div></li><ul><li><div>find neighbours of added node that have edges pointing to it —a(2,b),c(1,b)</div></li><li><div>c is visited, no other neighbours, so select a.</div></li><li><div>add a to set, update distance.</div></li><li><div>distance to c = b(1,c) + (distance a=>b) = b(1,c)+a(2,b) = a(3,c)</div></li><li><div>current distances:</div></li><ul><li><div>b(1,c)</div></li><li><div>a(3,c)</div></li></ul></ul><li><div>S = {a,b,c}, H = {d,e,f,g,h}</div></li><ul><li><div>find neighbours of added node that have edges pointing to it —b(2,a), d(1,a)</div></li><li><div>b is visited, no other neighbours, so select d.</div></li><li><div>add d to set, update distance.</div></li><li><div>distance to c = a(3,c) + (distance d=>a) = a(3,c) + d(1,a) = d(4,c)</div></li><li><div>current distances:</div></li><ul><li><div>b(1,c)</div></li><li><div>a(3,c)</div></li><li><div>d(4,c)</div></li></ul></ul><li><div>S = {a,b,c,d}, H = {e,f,g,h}</div></li></ol><ol><ul><li><div>etc.</div></li></ul></ol></ul><div style="margin-left: 80px;"><br/></div><div>Bellman-Ford algorithm</div><ul><li><div>allows weights to be negative</div></li><li><div>max n-1 iterations (with checking for negative cycle)</div></li><li><div>computes shortest path in rounds. each round tells you how many edges you can walk to reach the goal.</div></li><li><div><a href="https://www.youtube.com/watch?v=obWXjtg0L64&index=8&list=PL8WcC83XRlKJHk_bQLE-mEQRvdpflxHG2">this one is best explained with a video, which shows how to fill in one of the rows (you just have to make one row for each node)</a></div></li></ul><div><br/></div></body></html>